//
//  ProblemOffer42.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 42. 连续子数组的最大和
 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

 要求时间复杂度为O(n)。

 示例1:
     输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
     输出: 6
     解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

 提示：
     1 <= arr.length <= 10^5
     -100 <= arr[i] <= 100
 */
@objcMembers class ProblemOffer42: NSObject {
    func solution() {
        print(maxSubArrayClearAlloc([-2,1,-3,4,-1,2,1,-5,4]))
//        print(maxSubArray([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
    }
    
    /*
     动态规划
     1: 创建一个数组 dp[len]
     2: dp[i]以nums[i]结尾的最大值
     3: dp[i] = max(dp[i-1] + nums[i], nums[i])
     */
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return nums.count
        } else if nums.count == 1 {
            return nums[0]
        }
        
        var dp = Array(repeating: 0, count: nums.count)
        dp[0] = nums[0]
        
        for i in 1..<nums.count {
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        }
        print(dp)
        return dp.max() ?? nums.max() ?? 0
    }
    
    /*
     优化：dp[i]只与dp[i-1]有关
     */
    
    func maxSubArrayClearAlloc(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return nums.count
        } else if nums.count == 1 {
            return nums[0]
        }
        
        
        var maxValue = nums.max() ?? 0
        var lastValue = nums[0]
        
        for i in 1..<nums.count {
            lastValue = max(lastValue + nums[i], nums[i])
            maxValue = max(maxValue, lastValue)
        }
        
        return maxValue
    }
}
